package com.zlk.algorithm.dataStructure.tree.treeBase;

import com.zlk.algorithm.dataStructure.tree.NodeUtils;
import com.zlk.algorithm.dataStructure.tree.TreeNode;
import org.junit.Test;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: algorithm
 * @ClassName TreeMaxWidth
 * @description:树的最大宽度
 * @author: slfang
 * @create: 2024-02-26 17:05
 * @Version 1.0
 **/
public class TreeMaxWidth {


    /**
     * 一定要找好边界关系，变量设定要和逻辑保持一致，要清晰
     * @param node
     * @return
     */
    int maxWidth(TreeNode node){
        int max = 0;
        if(node==null){
            return max;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        TreeNode currEnd = node;
        TreeNode nextEnd = null;
        int count = 0;
        max =0;
        while (!queue.isEmpty()){
            TreeNode poll = queue.poll();
            if(poll.left!=null){
                queue.add(poll.left);
                nextEnd = poll.left;
            }
            if(poll.right!=null){
                queue.add(poll.right);
                nextEnd = poll.right;
            }
            count++;
            if(poll==currEnd){
                max = Math.max(max,count);
                count = 0;
                currEnd = nextEnd;
            }
        }
        return max;
    }


//    int maxWidth2(TreeNode node){
//        int max = 0;
//        if(node==null){
//            return max;
//        }
//        LinkedList<TreeNode> queue = new LinkedList<>();
//
//        queue.add(node);
//        TreeNode currRight = node;//当前层最右侧节点是谁
//        TreeNode nextRight = null;//下一个右侧节点是谁
//        int count = 0;//当前计数
//        max =0;
//        while (!queue.isEmpty()){
//            TreeNode poll = queue.poll();
//            count++;
//            if(poll==currRight){
//                max = Math.max(max,count);
//                count = 0;
//                currRight = nextMaxRight;
//            }
//            if(poll.left!=null){
//                queue.add(poll.left);
//                nextMaxRight = poll.left;
//            }
//            if(poll.right!=null){
//                queue.add(poll.right);
//                nextMaxRight = poll.right;
//            }
//        }
//        return max;
//    }


    public  int maxWidthUseMap(TreeNode head) {
        if (head == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(head);
        // key 在 哪一层，value
        HashMap<TreeNode, Integer> levelMap = new HashMap<>();
        levelMap.put(head, 1);
        int curLevel = 1; // 当前你正在统计哪一层的宽度
        int curLevelNodes = 0; // 当前层curLevel层，宽度目前是多少
        int max = 0;
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            int curNodeLevel = levelMap.get(cur);
            if (cur.left != null) {
                levelMap.put(cur.left, curNodeLevel + 1);
                queue.add(cur.left);
            }
            if (cur.right != null) {
                levelMap.put(cur.right, curNodeLevel + 1);
                queue.add(cur.right);
            }
            if (curNodeLevel == curLevel) {
                curLevelNodes++;
            } else {
                max = Math.max(max, curLevelNodes);
                curLevel++;
                curLevelNodes = 1;
            }
        }
        max = Math.max(max, curLevelNodes);
        return max;
    }

    //可能性
    //
    //信息

    /**
     * 树形dp方法
     * @return
     */
    public int maxWidthDp(TreeNode node){
        return -1;
    }

    @Test
    public void test(){
        int maxLevel = 10;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            TreeNode head = NodeUtils.generateRandomBST(maxLevel, maxValue);
            if (maxWidthUseMap(head) != maxWidth(head)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");

    }
}
